Hat Swaps
In the homework for my STEP program, I gave the following challenge problem.
Puzzle. My sages each wear a hat of a different color. As in standard hat puzzles, they can see everyone else’s hat color. Unlike in many other hat puzzles, they know the color of their own hat as well. I announce which color each of them should end up wearing; this assignment is a permutation of the original colors. Each sage is allowed one swap of hats with another person per day. They have two days to rearrange the hats so that everyone ends up with the correct color. Can they do it?
Many students noticed that the permutation can be decomposed into disjoint cycles and suggested solving the problem cycle by cycle. A few of them even pushed this idea all the way to a complete solution. However, none of them connected the puzzle to a topic we had discussed in class: dihedral groups.
Here is an elegant way to finish the solution once the permutation is decomposed into cycles. A cyclic permutation on n elements can be viewed as a rotation of an n-gon. Any rotation of an n-gon can be written as a product of two reflections. Each reflection of an n-gon, viewed as a permutation, consists only of 1- and 2-cycles. Ta-da!
Share:
Konstantin:
See also https://www.kvant.digital/problems/m1069/
5 March 2026, 2:29 pmStrahinja Petrovic:
Dear Dr. Khovanova,
I am a Principal DevOps Engineer from Serbia working for an American healthcare company. I have written a short work arguing that the Tarot de Marseille has a mathematical structure built into it, not on purpose, but because of how it was historically constructed.
I am looking for a mathematician to tell me if the math holds.
The larger context is documented on my website, a series of investigative articles on the historical fraud built around this object, including an unexamined asylum commitment from 1885 and a disputed authentication sold for sixty-five thousand euros – which gave me only friendly advice from people, as I may say.
Would you be willing to help me?
Thanks,
13 March 2026, 6:50 pmStrahinja